package com.xyhuo.leetcode;

public class Rob {

    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int one = cal(nums, 0, nums.length - 1);
        int two = cal(nums, 1, nums.length);
        return Math.max(one, two);
    }

    private int cal(int[] nums, int left, int right) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[left] = nums[left];
        for (int i = left + 1; i < right; i++) {
            int with = i - 2 >= 0 ? nums[i] + dp[i - 2] : nums[i];
            dp[i] = Math.max(with, dp[i - 1]);
        }
        return dp[right - 1];
    }
}
